#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "link_list.h"

/************************************************************************/
/*             以下是关于线性表链接存储（单链表）操作的16种算法        */
/************************************************************************/

/* 1.初始化线性表，即置单链表的表头指针为空 */
void initList(struct sNode* *hl)
{
    *hl = NULL;
    return;
}

/* 2.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
void clearList(struct sNode* *hl)
{
    /* cp和np分别作为指向两个相邻结点的指针 */
    struct sNode *cp, *np;
    cp = *hl;
    /* 遍历单链表，依次释放每个结点 */
    while(cp != NULL){
        np = cp->next;    /* 保存下一个结点的指针 */
        free(cp);
        cp = np;
    }
    *hl = NULL;        /* 置单链表的表头指针为空 */
    return;
}

/* 3.返回单链表的长度 */
int sizeList(struct sNode *hl)
{
    int count = 0;        /* 用于统计结点的个数 */
    while(hl != NULL){
        count++;
        hl = hl->next;
    }
    return count;
}

/* 4.检查单链表是否为空，若为空则返回１，否则返回０ */
int emptyList(struct sNode *hl)
{
    if(hl == NULL){
        return 1;
    }else{
        return 0;
    }
}

/* 5.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
int getElem(struct sNode *hl, int pos, struct sNode *pTemp)
{
    int i = 0;        /* 统计已遍历的结点个数 */
    if(pos < 1){
        printf("pos值非法，退出运行！ ");
        // exit(1);
        return -1;
    }
    while(hl != NULL){
        i++;
        if(i == pos){
            break;
        }
        hl = hl->next;
    }
    if(hl != NULL){
        pTemp->signal_level = hl->signal_level;
        strcpy(pTemp->essid, hl->essid);
        return 0;
        // return hl->data;
    }else{
        printf("pos值非法，退出运行！ ");
        // exit(1);
        return -1;
    }
}

/* 6.遍历一个单链表 */
void traverseList(struct sNode *hl)
{
    while(hl != NULL){
        printf("%s = %d\n", hl->essid, hl->signal_level);
        hl = hl->next;
    }
    printf(" ");
    return;
}

/* 7.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
int findList(struct sNode *hl, struct sNode *pTemp)
{
    while(hl != NULL){
        if(!strcmp(hl->essid, pTemp->essid)){
            pTemp->signal_level = hl->signal_level;
            return 1;
        }else{
            hl = hl->next;    
        }
    }
    return 0;
}

/* 8.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
// int updatePosList(struct sNode *hl, int pos, int x)
// {
//     int i = 0;
//     struct sNode *p = hl;
//     while(p != NULL){        /* 查找第pos个结点 */
//         i++;
//         if(pos == i){
//             break;
//         }else{
//             p = p->next;
//         }
//     }
//     if(pos == i){
//         p->data = x;
//         return 1;
//     }else{
//         return 0;
//     }
// }

/* 9.向单链表的表头插入一个元素 */
void insertFirstList(struct sNode* *hl, struct sNode *pTemp)
{
    struct sNode *newP;
    newP = malloc(sizeof(struct sNode));
    if(newP == NULL){
        printf("内存分配失败，退出运行！ ");
        exit(1);
    }
    newP->signal_level = pTemp->signal_level;        /* 把x的值赋给新结点的data域 */
    strcpy(newP->essid, pTemp->essid);
    /* 把新结点作为新的表头结点插入 */
    newP->next = *hl;        
    *hl = newP;
    return;
}

/* 10.向单链表的末尾添加一个元素 */
void insertLastList(struct sNode* *hl, struct sNode *pTemp)
{
    struct sNode *newP;
    newP = malloc(sizeof(struct sNode));
    if(newP == NULL){
        printf("内在分配失败，退出运行！ ");
        // exit(1);
    }
    /* 把x的值赋给新结点的data域，把空值赋给新结点的next域 */
    newP->signal_level = pTemp->signal_level;
    strcpy(newP->essid, pTemp->essid);
    newP->next = NULL;
    /* 若原表为空，则作为表头结点插入 */
    if(*hl == NULL){
        *hl = newP;        
    }
    /* 查找到表尾结点并完成插入 */
    else{
        struct sNode *p = NULL;
        while(p->next != NULL){
            p = p->next;
        }
        p->next = newP;
    }
    return;
}

/* 11.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */
int insetPosList(struct sNode* *hl, int pos, struct sNode *pTemp)
{
    int i = 0;
    struct sNode *newP;
    struct sNode *cp = *hl, *ap = NULL;
    /* 对pos值小于等于０的情况进行处理 */
    if(pos <= 0){
        printf("pos值非法，返回０表示插入失败！ ");
        return 0;
    }
    /* 查找第pos个结点 */
    while(cp != NULL){
        i++;
        if(pos == i){
            break;
        }else{
            ap = cp;
            cp = cp->next;
        }
    }
    /* 产生新结点，若分配失败，则停止插入 */
    newP = malloc(sizeof(struct sNode));
    if(newP == NULL){
        printf("内存分配失败，无法进行插入操作！ ");
        return 0;
    }
    /* 把x的值赋给新结点的data域 */
    newP->signal_level = pTemp->signal_level;
    strcpy(newP->essid, pTemp->essid);
    /* 把新结点插入到表头 */
    if(ap == NULL){
        newP->next = cp;        /* 或改为newP->next = *hl; */
        *hl = newP;
    }
    /* 把新结点插入到ap和cp之间 */
    else{
        newP->next = cp;
        ap->next = newP;
    }
    return 1;        /* 插入成功返回1 */
}

/* 12.向有序单链表中插入元素x结点，使得插入后仍然有序 */
void insertOrderList(struct sNode* *hl, struct sNode *pTemp)
{
    /* 把单链表的表头指针赋给cp，把ap置空 */
    struct sNode *cp = *hl, *ap = NULL;
    /* 建立新结点 */
    struct sNode *newP;
    newP = malloc(sizeof(struct sNode));
    if(newP == NULL){
        printf("内在分配失败，退出运行！ ");
        // exit(1);
    }
    newP->signal_level = pTemp->signal_level;        /* 把x的值赋给新结点的data域 */
    strcpy(newP->essid, pTemp->essid);
    /* 把新结点插入到表头 */
    if((cp == NULL) || (pTemp->signal_level > cp->signal_level)){
        newP->next = cp;
        *hl = newP;
        return;
    }
    /* 顺序查找出x结点的插入位置 */
    while(cp != NULL){
        if(pTemp->signal_level > cp->signal_level){
            break;
        }else{
            ap = cp;
            cp = cp->next;
        }
    }
    /* 把x结点插入到ap和cp之间 */
    newP->next = cp;
    ap->next = newP;
    return;
}

/* 13.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */
// int deleteFirstList(struct sNode* *hl)
// {
//     int temp;
//     struct sNode *p = *hl;        /* 暂存表头结点指针，以便回收 */
//     if(*hl == NULL){
//         printf("单链表为空，无表头可进行删除，退出运行！ ");
//         exit(1);
//     }
//     *hl = (*hl)->next;        /* 使表头指针指向第二个结点 */
//     temp = p->data;            /* 暂存原表头元素，以便返回 */
//     free(p);                /* 回收被删除的表头结点 */
//     return temp;            /* 返回第一个结点的值 */
// }

/* 14.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */
// int deleteLastList(struct sNode* *hl)
// {
//     int temp;
//     /* 初始化cp和ap指针，使cp指向表头结点，使ap为空 */
//     struct sNode *cp = *hl;
//     struct sNode *ap = NULL;
//     /* 单链表为空则停止运行 */
//     if(cp == NULL){
//         printf("单链表为空，无表头进行删除，退出运行！ ");
//         exit(1);
//     }
//     /* 从单链表中查找表尾结点，循环结束时cp指向表尾结点，ap指向其前驱结点 */
//     while(cp->next != NULL){
//         ap = cp;
//         cp = cp->next;
//     }
//     /* 若单链表中只有一个结点，则需要修改表头指针 */
//     if(ap == NULL){
//         *hl = (*hl)->next;        /* 或改为*hl = NULL; */
//     }
//     /* 删除表尾结点 */
//     else{
//         ap->next = NULL;
//     }
//     /* 暂存表尾元素，以便返回 */
//     temp = cp->data;
//     free(cp);        /* 回收被删除的表尾结点 */
//     return temp;        /* 返回表尾结点的值 */
// }

/* 15.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */
// int deletePosList(struct sNode* *hl, int pos)
// {
//     int i = 0;
//     int temp;
//     /* 初始化cp和ap指针，使cp指向表头结点，使ap为空 */
//     struct sNode *cp = *hl;
//     struct sNode *ap = NULL;
//     /* 单链表为空或pos值非法则停止运行 */
//     if((cp == NULL) || (pos <= 0)){
//         printf("单链表为空或pos值不正确，退出运行！ ");
//         exit(1);
//     }
//     /* 从单链表中查找第pos个结点，找到后由cp指向该结点，由ap指向其前驱结点 */
//     while(cp != NULL){
//         i++;
//         if(i == pos){
//             break;
//         }
//         ap = cp;
//         cp = cp->next;
//     }
//     /* 单链表中没有第pos个结点 */
//     if(cp == NULL){
//         printf("pos值不正确，退出运行！ ");
//         exit(1);
//     }
//     /* 若pos等于1，则需要删除表头结点 */
//     if(pos == 1){
//         *hl = (*hl)->next;        /* 或改为*hl = cp->next; */
//     }
//     /* 否则删除非表头结点，此时cp指向该结点，ap指向前驱结点 */
//     else{
//         ap->next = cp->next;
//     }
//     /* 暂存第pos个结点的值，以便返回 */
//     temp = cp->data;
//     free(cp);        /* 回收被删除的第pos个结点 */
//     return temp;    /* 返回在temp中暂存的第pos个结点的值 */
// }

/* 16.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
int deleteValueList(struct sNode* *hl, char *ssid)
{
    /* 初始化cp和ap指针，使cp指向表头结点，使ap为空 */
    struct sNode *cp = *hl;
    struct sNode *ap = NULL;
    /* 从单链表中查找值为x的结点，找到后由cp指向该结点，由ap指向其前驱结点 */
    while(cp != NULL){
        if(!strcmp(cp->essid, ssid)){
            break;
        }
        ap = cp;
        cp = cp->next;
    }
    /* 若查找失败，即该单链表中不存在值为x的结点，则返回0 */
    if(cp == NULL){
        return 0;
    }
    /* 如果删除的是表头或非表头结点则分别进行处理 */
    if(ap == NULL){
        *hl = (*hl)->next;        /* 或改为*hl= cp->next */
    }else{
        ap->next = cp->next;
    }
    free(cp);        /* 回收被删除的结点 */
    return 1;        /* 返回1表示删除成功 */
}

#if 0
/************************************************************************/
#define NN 12
#define MM 20
int main(int argc, char* argv[])
{
    int a[NN];
    int i;
    struct sNode *p, *h, *s;
    srand(time(NULL));
    initList(&p);
    for(i = 0; i < NN; i++){
        a[i] = rand() & MM;
    }
    printf("随机数序列：");
    for(i = 0; i < NN; i++){
        printf("%5d", a[i]);
    }
    printf("\n");

    printf("随机数逆序：");
    for(i = 0; i < NN; i++){
        insertFirstList(&p, a[i]);
    }
    traverseList(p);
    printf("\n");

    printf("单链表长度：%5d\n", sizeList(p));

    for(h = p; h != NULL; h = h->next){
        while(deleteValueList(&(h->next), h->data)){
            ;
        }
    }
    printf("去除重复数：");
    traverseList(p);
    printf("\n");

    printf("单链表长度：%5d\n", sizeList(p));

    h = NULL;
    for(s = p; s != NULL; s = s->next){
        insertOrderList(&h, s->data);
    }
    printf("有序表序列：");
    traverseList(h);
    printf("\n");

    clearList(&p);
    
    return 0;
}
#endif